Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11352 - Crazy king / 11352.cpp
blob9daffcc7084947cc15693edd1304fc4f5afc7a19
1 #include <iostream>
2 #include <climits>
3 #include <queue>
5 using namespace std;
7 char g[101][101];
9 int deltaCol[] = {-2, -1, 1, 2, 2, 1, -1, -2};
10 int deltaFil[] = {-1, -2, -2, -1, 1, 2, 2, 1};
12 int rdeltaCol[] = { -1, 0, 1, 1, 1, 0, -1, -1};
13 int rdeltaFil[] = { -1, -1, -1, 0, 1, 1, 1, 0};
15 int inicialCol, inicialFil;
17 char color[101][101];
18 unsigned int d[101][101];
20 int m, n; //m filas, n columnas
22 const int WHITE = 0;
23 const int GRAY = 1;
24 const int BLACK = 2;
26 void bfs(){
27 memset(color, WHITE, sizeof(color));
28 //memset(d, 2147483647, sizeof(d));
30 for (int i=0; i<=100; ++i) for (int j=0; j<=100; ++j) d[i][j] = UINT_MAX;
32 color[inicialFil][inicialCol] = GRAY;
33 d[inicialFil][inicialCol] = 0;
35 queue< pair<int,int> > q;
36 q.push(make_pair(inicialFil, inicialCol));
38 //printf("Empezando en: (%d,%d)\n", inicialFil, inicialCol);
40 while (!q.empty()){
41 int fil = q.front().first, col = q.front().second;
43 //printf("Saque el nodo (%d,%d) de la cola.\n", fil, col);
45 if (g[fil][col] == 'B'){
46 cout << "Minimal possible length of a trip is ";
47 cout << d[fil][col] << endl;
48 return;
51 for (int k=0; k<8; ++k){
52 int tempFil, tempCol;
53 tempFil = fil + rdeltaFil[k];
54 tempCol = col + rdeltaCol[k];
55 //if (tempFil >= 0 && tempFil < m && tempCol >= 0 && tempCol < n){
56 if ( (tempFil >= 0) && (tempFil < m) && (tempCol >= 0) && (tempCol < n)){
57 char c = g[tempFil][tempCol];
59 //printf("Considerando para marcado el nodo(%d,%d) que contiene %c\n", tempFil, tempCol, c);
61 if (c != 'Z' && c != 'X'){
63 //printf("Nodo visitable (%d,%d), revisando que sea blanco.\n", tempFil, tempCol);
65 if (color[tempFil][tempCol] == WHITE){
66 color[tempFil][tempCol] = GRAY;
68 //printf("Marcando gris el nodo (%d,%d)\n", tempFil, tempCol);
70 d[tempFil][tempCol] = d[fil][col] + 1;
71 q.push(make_pair(tempFil, tempCol));
76 q.pop();
77 color[fil][col] = BLACK;
79 printf("King Peter, you can't go now!\n");
83 int main(){
84 int casos;
85 cin >> casos;
86 while (casos--){
87 cin >> m >> n;
88 for (int i=0; i<m; ++i){
89 for (int j=0; j<n; ++j){
90 char c;
91 cin >> c;
92 g[i][j] = c;
93 if (c == 'A'){
94 inicialFil = i;
95 inicialCol = j;
102 for (int i=0; i<m; ++i){
103 for (int j=0; j<n; ++j){
104 if (g[i][j] == 'Z'){
105 for (int k=0; k<8; ++k){
106 int tempFil, tempCol;
107 tempFil = i + deltaFil[k];
108 tempCol = j + deltaCol[k];
109 if (tempFil >= 0 && tempFil <= m && tempCol >=0 && tempCol < n){
110 char c = g[tempFil][tempCol];
111 if (c != 'B' && c != 'A' && c != 'Z') g[tempFil][tempCol] = 'X';
118 //En este momento, g[i][j] contiene una X si es una casilla atacable
120 bfs();
123 /*for (int i=0; i<m; ++i){
124 for (int j=0; j<n; ++j){
125 cerr << g[i][j];
127 cerr << endl;
129 cerr << endl;